// 2016蓝桥杯真题-第六题 方格填数
// https://blog.csdn.net/JSY1997/article/details/79467708 如下的10个格子填入0-9
// 的数字。要求：连续的两个数字不能相邻。
// 左右、上下、对角都算相邻,一共有多少种可能的填数方案？
// 请填写表示方案数目的整数。答案1580
//   |x|x|x|
// |x|x|x|x|
// |x|x|x|
// 当作不可以重复使用来处理的。

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

int checkConnect(const vector<int>& arr) {
  //横向
  if (abs(arr[0] - arr[1]) != 1 && abs(arr[1] - arr[2]) != 1 &&
      abs(arr[3] - arr[4]) != 1 && abs(arr[4] - arr[5]) != 1 &&
      abs(arr[5] - arr[6]) != 1 && abs(arr[7] - arr[8]) != 1 &&
      abs(arr[8] - arr[9]) != 1 && abs(arr[3] - arr[7]) != 1 &&
      abs(arr[0] - arr[4]) != 1 && abs(arr[4] - arr[8]) != 1 &&
      abs(arr[1] - arr[5]) != 1 && abs(arr[5] - arr[9]) != 1 &&
      //纵向
      abs(arr[2] - arr[6]) != 1 && abs(arr[3] - arr[8]) != 1 &&
      abs(arr[4] - arr[9]) != 1 && abs(arr[0] - arr[5]) != 1 &&
      //右斜
      abs(arr[1] - arr[6]) != 1 && abs(arr[0] - arr[3]) != 1 &&
      abs(arr[1] - arr[4]) != 1 && abs(arr[4] - arr[7]) != 1 &&
      abs(arr[2] - arr[5]) != 1 && abs(arr[5] - arr[8]) != 1 &&
      //左斜
      abs(arr[6] - arr[9]) != 1) {
    return 1;
  }
  return 0;
}

void dfs(size_t iPos, vector<int>& arr, vector<int> vtVisited, int& res) {
  if (iPos == arr.size()) {
    res++;
    return;
  }
  for (size_t i = 0; i < arr.size(); i++) {
    if (vtVisited[i]) continue;
    vtVisited[i] == 1;
    arr[iPos] = i;
    dfs(iPos + 1, arr, vtVisited, res);
    vtVisited[i] == 0;
  }
}

void dfs2(vector<int>& arr, int iPos, vector<int>& vtVisit, int& res) {
  if (iPos > 9) {
    if (checkConnect(arr)) {
      res++;
    }
    return;
  }
  for (int i = 0; i <= 9; i++) {
    if (vtVisit[i]) {
      continue;
    }
    vtVisit[i] = 1;
    arr[iPos] = i;
    dfs2(arr, iPos + 1, vtVisit, res);
    vtVisit[i] = 0;
  }
  return;
}

int getCount_stl(vector<int> arr) {
  int count = 0;
  do {
    if (checkConnect(arr)) count++;
  } while (next_permutation(arr.begin(), arr.end()));
  printf("%d\n", count);
  return count;
}

int getCount_dfs(vector<int> arr) {
  vector<int> vtVisit(10);  // vtVisited[i] = 1 表示i已经访问过
  int nCnt = 0;
  dfs2(arr, 0, vtVisit, nCnt);  // dfs(0, arr, {}, count); 错误
  cout << nCnt;
  return nCnt;
}

int main() {
  getCount_stl({0, 1, 2, 3, 4, 5, 6, 7, 8, 9});
  getCount_dfs({0, 1, 2, 3, 4, 5, 6, 7, 8, 9});
  return 0;
}
